<!DOCTYPE html>
<html lang="zh-CN">
    <head>
        <meta charset="utf-8">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="robots" content="noodp" />
        <title>PAT甲级--Insertion-or-Heap-Sort - L_B__</title><meta name="referrer" content="no-referrer">
<meta name="description" content="PAT甲级--Insertion-or-Heap-Sort"><meta property="og:title" content="PAT甲级--Insertion-or-Heap-Sort" />
<meta property="og:description" content="PAT甲级--Insertion-or-Heap-Sort" />
<meta property="og:type" content="article" />
<meta property="og:url" content="https://acking-you.github.io/posts/pat%E7%94%B2%E7%BA%A7-insertion-or-heap-sort/" /><meta property="og:image" content="https://acking-you.github.io/logo.png"/><meta property="article:section" content="posts" />
<meta property="article:published_time" content="2022-02-19T00:00:00+00:00" />
<meta property="article:modified_time" content="2022-02-19T00:00:00+00:00" />

<meta name="twitter:card" content="summary_large_image"/>
<meta name="twitter:image" content="https://acking-you.github.io/logo.png"/>

<meta name="twitter:title" content="PAT甲级--Insertion-or-Heap-Sort"/>
<meta name="twitter:description" content="PAT甲级--Insertion-or-Heap-Sort"/>
<meta name="application-name" content="FeelIt">
<meta name="apple-mobile-web-app-title" content="FeelIt"><meta name="theme-color" content="#ffffff"><meta name="msapplication-TileColor" content="#da532c"><link rel="canonical" href="https://acking-you.github.io/posts/pat%E7%94%B2%E7%BA%A7-insertion-or-heap-sort/" /><link rel="prev" href="https://acking-you.github.io/posts/%E5%A0%86%E7%9A%84%E8%BF%90%E7%94%A8%E6%9C%89%E5%BA%8F%E5%85%83%E7%B4%A0%E7%9A%84%E5%A4%9A%E8%B7%AF%E5%BD%92%E5%B9%B6topk%E9%97%AE%E9%A2%98/" /><link rel="next" href="https://acking-you.github.io/posts/java%E5%8A%A8%E6%80%81%E4%BB%A3%E7%90%86%E8%AF%A6%E8%A7%A3/" /><link rel="stylesheet" href="/css/page.min.css"><link rel="stylesheet" href="/css/home.min.css"><script type="application/ld+json">
    {
        "@context": "http://schema.org",
        "@type": "BlogPosting",
        "headline": "PAT甲级--Insertion-or-Heap-Sort",
        "inLanguage": "zh-CN",
        "mainEntityOfPage": {
            "@type": "WebPage",
            "@id": "https:\/\/acking-you.github.io\/posts\/pat%E7%94%B2%E7%BA%A7-insertion-or-heap-sort\/"
        },"genre": "posts","keywords": "PAT甲级--Insertion-or-Heap-Sort","wordcount":  1669 ,
        "url": "https:\/\/acking-you.github.io\/posts\/pat%E7%94%B2%E7%BA%A7-insertion-or-heap-sort\/","datePublished": "2022-02-19T00:00:00+00:00","dateModified": "2022-02-19T00:00:00+00:00","publisher": {
            "@type": "Organization",
            "name": "作者"},"author": {
                "@type": "Person",
                "name": "作者"
            },"description": "PAT甲级--Insertion-or-Heap-Sort"
    }
    </script></head><body data-header-desktop="auto" data-header-mobile="auto"><script>(window.localStorage && localStorage.getItem('theme') ? localStorage.getItem('theme') === 'dark' : ('auto' === 'auto' ? window.matchMedia('(prefers-color-scheme: dark)').matches : 'auto' === 'dark')) && document.body.setAttribute('theme', 'dark');</script>

        <div id="mask"></div><div class="wrapper"><header class="desktop" id="header-desktop">
    <div class="header-wrapper">
        <div class="header-title">
            <a href="/" title="L_B__">L_B__</a>
        </div>
        <div class="menu">
            <div class="menu-inner"><a class="menu-item" href="/posts/"> 文章 </a><a class="menu-item" href="/tags/"> 标签 </a><a class="menu-item" href="/categories/"> 分类 </a><span class="menu-item delimiter"></span><span class="menu-item search" id="search-desktop">
                        <input type="text" placeholder="搜索文章标题或内容..." id="search-input-desktop">
                        <a href="#" class="search-button search-toggle" id="search-toggle-desktop" title="搜索">
                            <i class="fas fa-search fa-fw"></i>
                        </a>
                        <a href="#" class="search-button search-clear" id="search-clear-desktop" title="清空">
                            <i class="fas fa-times-circle fa-fw"></i>
                        </a>
                        <span class="search-button search-loading" id="search-loading-desktop">
                            <i class="fas fa-spinner fa-fw fa-spin"></i>
                        </span>
                    </span><a href="javascript:void(0);" class="menu-item theme-switch" title="切换主题">
                    <i class="fas fa-adjust fa-fw"></i>
                </a>
            </div>
        </div>
    </div>
</header><header class="mobile" id="header-mobile">
    <div class="header-container">
        <div class="header-wrapper">
            <div class="header-title">
                <a href="/" title="L_B__">L_B__</a>
            </div>
            <div class="menu-toggle" id="menu-toggle-mobile">
                <span></span><span></span><span></span>
            </div>
        </div>
        <div class="menu" id="menu-mobile"><div class="search-wrapper">
                    <div class="search mobile" id="search-mobile">
                        <input type="text" placeholder="搜索文章标题或内容..." id="search-input-mobile">
                        <a href="#" class="search-button search-toggle" id="search-toggle-mobile" title="搜索">
                            <i class="fas fa-search fa-fw"></i>
                        </a>
                        <a href="#" class="search-button search-clear" id="search-clear-mobile" title="清空">
                            <i class="fas fa-times-circle fa-fw"></i>
                        </a>
                        <span class="search-button search-loading" id="search-loading-mobile">
                            <i class="fas fa-spinner fa-fw fa-spin"></i>
                        </span>
                    </div>
                    <a href="#" class="search-cancel" id="search-cancel-mobile">
                        取消
                    </a>
                </div><a class="menu-item" href="/posts/" title="">文章</a><a class="menu-item" href="/tags/" title="">标签</a><a class="menu-item" href="/categories/" title="">分类</a><div class="menu-item"><a href="javascript:void(0);" class="theme-switch" title="切换主题">
                    <i class="fas fa-adjust fa-fw"></i>
                </a>
            </div></div>
    </div>
</header><div class="search-dropdown desktop">
    <div id="search-dropdown-desktop"></div>
</div>
<div class="search-dropdown mobile">
    <div id="search-dropdown-mobile"></div>
</div><main class="main">
                <div class="container"><div class="toc" id="toc-auto">
            <h2 class="toc-title">目录</h2>
            <div class="toc-content" id="toc-content-auto"></div>
        </div><article class="page single" data-toc="disable"><div class="featured-image"><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/d42c44f8494c4416af716bc7156a4c96.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/d42c44f8494c4416af716bc7156a4c96.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/d42c44f8494c4416af716bc7156a4c96.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/d42c44f8494c4416af716bc7156a4c96.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/d42c44f8494c4416af716bc7156a4c96.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="PAT甲级--Insertion-or-Heap-Sort" /></div><div class="single-card" data-image="true"><h2 class="single-title animated flipInX">PAT甲级--Insertion-or-Heap-Sort</h2><div class="post-meta">
                <div class="post-meta-line"><span class="post-author"><a href="/" title="Author" rel=" author" class="author"><i class="fas fa-user-circle fa-fw"></i>作者</a></span>&nbsp;<span class="post-category">出版于  <a href="/categories/%E7%AE%97%E6%B3%95%E6%8E%92%E5%BA%8F%E5%8E%9F%E7%90%86%E8%BF%90%E7%94%A8/"><i class="far fa-folder fa-fw"></i>算法——排序原理运用</a></span></div>
                <div class="post-meta-line"><span><i class="far fa-calendar-alt fa-fw"></i>&nbsp;<time datetime="2022-02-19">2022-02-19</time></span>&nbsp;<span><i class="fas fa-pencil-alt fa-fw"></i>&nbsp;约 1669 字</span>&nbsp;
                    <span><i class="far fa-clock fa-fw"></i>&nbsp;预计阅读 4 分钟</span>&nbsp;</div>
            </div>
            
            <hr><div class="details toc" id="toc-static"  data-kept="">
                    <div class="details-summary toc-title">
                        <span>目录</span>
                        <span><i class="details-icon fas fa-angle-right"></i></span>
                    </div>
                    <div class="details-content toc-content" id="toc-content-static"><nav id="TableOfContents">
  <ul>
    <li><a href="#题目">题目</a></li>
    <li><a href="#题目大意">题目大意</a></li>
    <li><a href="#解题代码拆解">解题代码拆解</a>
      <ul>
        <li><a href="#关键的判断函数">关键的判断函数</a></li>
        <li><a href="#堆排序和插入排序">堆排序和插入排序</a></li>
        <li><a href="#整合代码进行提交">整合代码进行提交</a></li>
      </ul>
    </li>
  </ul>
</nav></div>
                </div><div class="content" id="content"><h2 id="题目">题目</h2>
<p><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/906d50127f2a4071b3b88998d3fc12ac.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/906d50127f2a4071b3b88998d3fc12ac.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/906d50127f2a4071b3b88998d3fc12ac.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/906d50127f2a4071b3b88998d3fc12ac.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/906d50127f2a4071b3b88998d3fc12ac.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/906d50127f2a4071b3b88998d3fc12ac.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
<p><a href="https://www.nowcoder.com/pat/5/problem/4322" target="_blank" rel="noopener noreffer">OJ平台</a></p>
<h2 id="题目大意">题目大意</h2>
<ul>
<li>有很多题目实际不需要看懂题目，只需要看懂输入和输出，比如这题。</li>
</ul>
<blockquote>
<p>此题虽然题目较为学术，且比较长，实际总结下来就是，通过给你一个原数组序列，还有一个用插入排序或者是堆排序排了几轮的数组序列，你要根据这个序列判断所使用的排序方式，并且再以该排序方式往下排一轮。</p>
</blockquote>
<h2 id="解题代码拆解">解题代码拆解</h2>
<blockquote>
<p>这次由于我使用的接口化函数设计，也就是传入指针进行操作，没有采用全局变量，所以直接input操作写在main函数里面，省空间。</p>
</blockquote>
<h3 id="关键的判断函数">关键的判断函数</h3>
<p><strong>isInsert()</strong></p>
<blockquote>
<p>设计思路：假设为插入排序后的序列，通过一次循环，找到下一个要被排序的元素位置，按理来说，没有被排序的位置应该和原数组的序列情况一致，如果不一致，则不是插入排序。</p>
</blockquote>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="c1">//用于确定是否为插入排序，顺便返回此时待插入处理的位置
</span><span class="c1"></span><span class="kt">int</span> <span class="nf">isInsert</span><span class="p">(</span><span class="kt">int</span><span class="o">*</span> <span class="n">nums</span><span class="p">,</span> <span class="kt">int</span> <span class="n">len</span><span class="p">)</span> <span class="p">{</span>
    <span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
    <span class="k">for</span> <span class="p">(;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">len</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]</span> <span class="o">&gt;</span> <span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">])</span>
            <span class="k">break</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">len</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">original</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">!=</span> <span class="n">nums</span><span class="p">[</span><span class="n">j</span><span class="p">])</span>
            <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="n">i</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h3 id="堆排序和插入排序">堆排序和插入排序</h3>
<h4 id="插入排序">插入排序</h4>
<blockquote>
<p>插入排序很简单，我这里直接写插入排序的每一轮处理函数来代替。</p>
</blockquote>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="c1">//插入排序的单步处理
</span><span class="c1"></span><span class="kt">void</span> <span class="nf">InsertSort</span><span class="p">(</span><span class="kt">int</span><span class="o">*</span> <span class="n">nums</span><span class="p">,</span> <span class="kt">int</span> <span class="n">numSize</span><span class="p">,</span> <span class="kt">int</span> <span class="n">i</span><span class="p">)</span> <span class="p">{</span>
    <span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">temp</span> <span class="o">=</span> <span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
    <span class="k">for</span> <span class="p">(;</span> <span class="n">j</span> <span class="o">&gt;</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">nums</span><span class="p">[</span><span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]</span> <span class="o">&gt;</span> <span class="n">temp</span><span class="p">;</span> <span class="n">j</span><span class="o">--</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">nums</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">nums</span><span class="p">[</span><span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="p">];</span>
    <span class="p">}</span>
    <span class="n">nums</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">temp</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h4 id="堆排序">堆排序</h4>
<p>堆排序的原理：</p>
<blockquote>
<p>对于一个完整的堆排序，分为两个过程：堆化+维持堆化。
建立大根堆，每次堆化找到最大值，为了维持堆的结构和排序，将堆顶与最后一个元素交换，然后更新堆的范围到 <code>0~i-1</code> 再次堆化，又能找到这个堆中的最大值，长此以往，便完成了排序。</p>
</blockquote>
<ul>
<li>对于堆排序中的每一轮：堆排中的每一轮都是缩小堆的范围，并继续维持大根堆，在堆范围以外的元素就是被排好的元素。所以重点在于从后往前找到已经排到了哪个位置，再进行一次交换和堆化便可完成一轮排序。</li>
</ul>
<p><strong>堆排的过程</strong>：</p>
<blockquote>
<p>向下堆化的函数：sift_down()</p>
</blockquote>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="c1">//堆化，得到大根堆
</span><span class="c1">//对于从0开始编号的二叉堆:
</span><span class="c1"></span><span class="cm">/* iparent = (i-1)/2,
</span><span class="cm">ilchild = i*2+1,
</span><span class="cm">irchild = i*2+2 */</span>
<span class="kt">void</span> <span class="nf">sift_down</span><span class="p">(</span><span class="kt">int</span> <span class="n">arr</span><span class="p">[],</span> <span class="kt">int</span> <span class="n">start</span><span class="p">,</span> <span class="kt">int</span> <span class="n">end</span><span class="p">)</span> <span class="p">{</span> <span class="c1">// 计算父结点和子结点的下标
</span><span class="c1"></span>    <span class="kt">int</span> <span class="n">parent</span> <span class="o">=</span> <span class="n">start</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">child</span> <span class="o">=</span> <span class="n">parent</span> <span class="o">*</span> <span class="mi">2</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">child</span> <span class="o">&lt;=</span> <span class="n">end</span><span class="p">)</span> <span class="p">{</span> <span class="c1">// 子结点下标在范围内才做比较
</span><span class="c1">// 先比较两个子结点大小，选择最大的
</span><span class="c1"></span>        <span class="k">if</span> <span class="p">(</span><span class="n">child</span> <span class="o">+</span> <span class="mi">1</span> <span class="o">&lt;=</span> <span class="n">end</span> <span class="o">&amp;&amp;</span> <span class="n">arr</span><span class="p">[</span><span class="n">child</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">arr</span><span class="p">[</span><span class="n">child</span> <span class="o">+</span> <span class="mi">1</span><span class="p">])</span> <span class="n">child</span><span class="o">++</span><span class="p">;</span>
<span class="c1">// 如果父结点比子结点大，代表调整完毕，直接跳出函数
</span><span class="c1"></span>        <span class="k">if</span> <span class="p">(</span><span class="n">arr</span><span class="p">[</span><span class="n">parent</span><span class="p">]</span> <span class="o">&gt;=</span> <span class="n">arr</span><span class="p">[</span><span class="n">child</span><span class="p">])</span> <span class="k">return</span><span class="p">;</span>
        <span class="k">else</span> <span class="p">{</span>
<span class="c1">// 否则交换父子内容，子结点再和孙结点比较
</span><span class="c1"></span>            <span class="n">swap</span><span class="p">(</span><span class="n">arr</span><span class="p">[</span><span class="n">parent</span><span class="p">],</span> <span class="n">arr</span><span class="p">[</span><span class="n">child</span><span class="p">]);</span>
            <span class="n">parent</span> <span class="o">=</span> <span class="n">child</span><span class="p">;</span>
            <span class="n">child</span> <span class="o">=</span> <span class="n">parent</span> <span class="o">*</span> <span class="mi">2</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>
<span class="p">}</span>
</code></pre></div><blockquote>
<p>先完全堆化，再利用它挑选最大值维持堆化的过程：heap_sort()</p>
</blockquote>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="kt">void</span> <span class="nf">heap_sort</span><span class="p">(</span><span class="kt">int</span> <span class="n">arr</span><span class="p">[],</span> <span class="kt">int</span> <span class="n">len</span><span class="p">)</span> <span class="p">{</span>
<span class="c1">// 从最后一个节点的父节点开始 sift down 以完成堆化 (heapify)
</span><span class="c1"></span>   <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="p">(</span><span class="n">len</span> <span class="o">-</span> <span class="mi">1</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">)</span>
       <span class="n">sift_down</span><span class="p">(</span><span class="n">arr</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="n">len</span> <span class="o">-</span> <span class="mi">1</span><span class="p">);</span>
<span class="c1">// 先将第一个元素和已经排好的元素前一位做交换，再重新调整（刚调整的元素之前的元素），直到排序完毕
</span><span class="c1"></span>   <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">len</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">)</span> <span class="p">{</span>
       <span class="n">swap</span><span class="p">(</span><span class="n">arr</span><span class="p">[</span><span class="mi">0</span><span class="p">],</span> <span class="n">arr</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span>
       <span class="n">sift_down</span><span class="p">(</span><span class="n">arr</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">);</span>
   <span class="p">}</span>
<span class="p">}</span>
</code></pre></div><p><strong>方便更新下一轮堆排的工具</strong>：</p>
<blockquote>
<p>确定堆排序到哪个位置的函数：findP</p>
</blockquote>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="c1">//由于堆排是从后往前先得出最大值，所以直接从后往前判断最大值位置即可得出堆排排到了哪一轮
</span><span class="c1"></span><span class="kt">int</span> <span class="nf">findP</span><span class="p">(</span><span class="kt">int</span><span class="o">*</span> <span class="n">nums</span><span class="p">,</span> <span class="kt">int</span> <span class="n">len</span><span class="p">)</span> <span class="p">{</span>
    <span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
    <span class="k">for</span> <span class="p">(;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">len</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
        <span class="kt">int</span> <span class="n">val</span> <span class="o">=</span> <span class="o">*</span><span class="n">max_element</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="n">nums</span> <span class="o">+</span> <span class="n">len</span> <span class="o">-</span> <span class="n">i</span><span class="p">);</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">len</span> <span class="o">-</span> <span class="mi">1</span> <span class="o">-</span> <span class="n">i</span><span class="p">]</span> <span class="o">!=</span> <span class="n">val</span><span class="p">)</span>
            <span class="k">break</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="n">len</span> <span class="o">-</span> <span class="mi">1</span> <span class="o">-</span> <span class="n">i</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h3 id="整合代码进行提交">整合代码进行提交</h3>
<blockquote>
<p>效率还行！
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/ecf9c3bd535049159cbc1116bbf57331.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/ecf9c3bd535049159cbc1116bbf57331.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/ecf9c3bd535049159cbc1116bbf57331.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/ecf9c3bd535049159cbc1116bbf57331.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/ecf9c3bd535049159cbc1116bbf57331.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/ecf9c3bd535049159cbc1116bbf57331.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
</blockquote>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="cp">#include</span> <span class="cpf">&lt;bits/stdc++.h&gt;</span><span class="cp">
</span><span class="cp"></span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
<span class="kt">int</span><span class="o">*</span> <span class="n">original</span> <span class="o">=</span> <span class="k">nullptr</span><span class="p">;</span>
<span class="c1">//插入排序的单步处理
</span><span class="c1"></span><span class="kt">void</span> <span class="nf">InsertSort</span><span class="p">(</span><span class="kt">int</span><span class="o">*</span> <span class="n">nums</span><span class="p">,</span> <span class="kt">int</span> <span class="n">numSize</span><span class="p">,</span> <span class="kt">int</span> <span class="n">i</span><span class="p">)</span> <span class="p">{</span>
    <span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">temp</span> <span class="o">=</span> <span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
    <span class="k">for</span> <span class="p">(;</span> <span class="n">j</span> <span class="o">&gt;</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">nums</span><span class="p">[</span><span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]</span> <span class="o">&gt;</span> <span class="n">temp</span><span class="p">;</span> <span class="n">j</span><span class="o">--</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">nums</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">nums</span><span class="p">[</span><span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="p">];</span>
    <span class="p">}</span>
    <span class="n">nums</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">temp</span><span class="p">;</span>
<span class="p">}</span>


<span class="c1">//堆排序
</span><span class="c1"></span><span class="kt">void</span> <span class="nf">sift_down</span><span class="p">(</span><span class="kt">int</span> <span class="n">arr</span><span class="p">[],</span> <span class="kt">int</span> <span class="n">start</span><span class="p">,</span> <span class="kt">int</span> <span class="n">end</span><span class="p">)</span> <span class="p">{</span> <span class="c1">// 计算父结点和子结点的下标
</span><span class="c1"></span>    <span class="kt">int</span> <span class="n">parent</span> <span class="o">=</span> <span class="n">start</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">child</span> <span class="o">=</span> <span class="n">parent</span> <span class="o">*</span> <span class="mi">2</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">child</span> <span class="o">&lt;=</span> <span class="n">end</span><span class="p">)</span> <span class="p">{</span> <span class="c1">// 子结点下标在范围内才做比较
</span><span class="c1">// 先比较两个子结点大小，选择最大的
</span><span class="c1"></span>        <span class="k">if</span> <span class="p">(</span><span class="n">child</span> <span class="o">+</span> <span class="mi">1</span> <span class="o">&lt;=</span> <span class="n">end</span> <span class="o">&amp;&amp;</span> <span class="n">arr</span><span class="p">[</span><span class="n">child</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">arr</span><span class="p">[</span><span class="n">child</span> <span class="o">+</span> <span class="mi">1</span><span class="p">])</span> <span class="n">child</span><span class="o">++</span><span class="p">;</span>
<span class="c1">// 如果父结点比子结点大，代表调整完毕，直接跳出函数
</span><span class="c1"></span>        <span class="k">if</span> <span class="p">(</span><span class="n">arr</span><span class="p">[</span><span class="n">parent</span><span class="p">]</span> <span class="o">&gt;=</span> <span class="n">arr</span><span class="p">[</span><span class="n">child</span><span class="p">])</span> <span class="k">return</span><span class="p">;</span>
        <span class="k">else</span> <span class="p">{</span>
<span class="c1">// 否则交换父子内容，子结点再和孙结点比较
</span><span class="c1"></span>            <span class="n">swap</span><span class="p">(</span><span class="n">arr</span><span class="p">[</span><span class="n">parent</span><span class="p">],</span> <span class="n">arr</span><span class="p">[</span><span class="n">child</span><span class="p">]);</span>
            <span class="n">parent</span> <span class="o">=</span> <span class="n">child</span><span class="p">;</span>
            <span class="n">child</span> <span class="o">=</span> <span class="n">parent</span> <span class="o">*</span> <span class="mi">2</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>
<span class="p">}</span>

<span class="c1">//用于找出堆排已经拍到了哪个位置的最大值。
</span><span class="c1"></span><span class="kt">int</span> <span class="nf">findP</span><span class="p">(</span><span class="kt">int</span><span class="o">*</span> <span class="n">nums</span><span class="p">,</span> <span class="kt">int</span> <span class="n">len</span><span class="p">)</span> <span class="p">{</span>
    <span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
    <span class="k">for</span> <span class="p">(;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">len</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
        <span class="kt">int</span> <span class="n">val</span> <span class="o">=</span> <span class="o">*</span><span class="n">max_element</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="n">nums</span> <span class="o">+</span> <span class="n">len</span> <span class="o">-</span> <span class="n">i</span><span class="p">);</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">len</span> <span class="o">-</span> <span class="mi">1</span> <span class="o">-</span> <span class="n">i</span><span class="p">]</span> <span class="o">!=</span> <span class="n">val</span><span class="p">)</span>
            <span class="k">break</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="n">len</span> <span class="o">-</span> <span class="mi">1</span> <span class="o">-</span> <span class="n">i</span><span class="p">;</span>
<span class="p">}</span>

<span class="c1">//用于确定是否为插入排序，顺便返回此时待插入处理的位置
</span><span class="c1"></span><span class="kt">int</span> <span class="nf">isInsert</span><span class="p">(</span><span class="kt">int</span><span class="o">*</span> <span class="n">nums</span><span class="p">,</span> <span class="kt">int</span> <span class="n">len</span><span class="p">)</span> <span class="p">{</span>
    <span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
    <span class="k">for</span> <span class="p">(;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">len</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]</span> <span class="o">&gt;</span> <span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">])</span>
            <span class="k">break</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">len</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">original</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">!=</span> <span class="n">nums</span><span class="p">[</span><span class="n">j</span><span class="p">])</span>
            <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="n">i</span><span class="p">;</span>
<span class="p">}</span>
<span class="c1">//统一打印结果函数
</span><span class="c1"></span><span class="kt">void</span> <span class="nf">print</span><span class="p">(</span><span class="kt">int</span><span class="o">*</span> <span class="n">nums</span><span class="p">,</span> <span class="kt">int</span> <span class="n">len</span><span class="p">)</span> <span class="p">{</span>
    <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">nums</span><span class="p">[</span><span class="mi">0</span><span class="p">];</span>
    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">len</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="sc">&#39; &#39;</span> <span class="o">&lt;&lt;</span> <span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
    <span class="p">}</span>
<span class="p">}</span>
<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span>
    <span class="c1">//@输入处理
</span><span class="c1"></span>    <span class="n">ios</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span>
    <span class="kt">int</span> <span class="n">N</span><span class="p">;</span>
    <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">N</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">org</span><span class="p">[</span><span class="n">N</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">N</span><span class="p">];</span>
    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">N</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">org</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
    <span class="p">}</span> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">N</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
    <span class="p">}</span>
    <span class="c1">//@根据不同的排序方式进行答案的打印
</span><span class="c1"></span>    <span class="n">original</span> <span class="o">=</span> <span class="n">org</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">flag</span> <span class="o">=</span> <span class="n">isInsert</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="n">N</span><span class="p">);</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">flag</span> <span class="o">!=</span> <span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">&#34;Insertion Sort&#34;</span> <span class="o">&lt;&lt;</span> <span class="n">endl</span><span class="p">;</span>
        <span class="n">InsertSort</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="n">N</span><span class="p">,</span> <span class="n">flag</span><span class="p">);</span>
        <span class="n">print</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="n">N</span><span class="p">);</span>
    <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
        <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">&#34;Heap Sort&#34;</span> <span class="o">&lt;&lt;</span> <span class="n">endl</span><span class="p">;</span>
        <span class="kt">int</span> <span class="n">pos</span> <span class="o">=</span> <span class="n">findP</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="n">N</span><span class="p">);</span>
        <span class="n">swap</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="mi">0</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">pos</span><span class="p">]);</span>
        <span class="n">sift_down</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="n">pos</span> <span class="o">-</span> <span class="mi">1</span><span class="p">);</span>
        <span class="n">print</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="n">N</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div></div><div class="post-footer" id="post-footer">
    <div class="post-info"><div class="post-info-tag"><span><a href="/tags/pat%E7%94%B2%E7%BA%A7-insertion-or-heap-sort/">PAT甲级--Insertion-or-Heap-Sort</a>
                </span></div><div class="post-info-line"><div class="post-info-mod">
                <span>更新于 2022-02-19</span>
            </div><div class="post-info-mod"></div>
        </div><div class="post-info-share">
            <span><a href="javascript:void(0);" title="分享到 Twitter" data-sharer="twitter" data-url="https://acking-you.github.io/posts/pat%E7%94%B2%E7%BA%A7-insertion-or-heap-sort/" data-title="PAT甲级--Insertion-or-Heap-Sort" data-hashtags="PAT甲级--Insertion-or-Heap-Sort"><i class="fab fa-twitter fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Facebook" data-sharer="facebook" data-url="https://acking-you.github.io/posts/pat%E7%94%B2%E7%BA%A7-insertion-or-heap-sort/" data-hashtag="PAT甲级--Insertion-or-Heap-Sort"><i class="fab fa-facebook-square fa-fw"></i></a><a href="javascript:void(0);" title="分享到 WhatsApp" data-sharer="whatsapp" data-url="https://acking-you.github.io/posts/pat%E7%94%B2%E7%BA%A7-insertion-or-heap-sort/" data-title="PAT甲级--Insertion-or-Heap-Sort" data-web><i class="fab fa-whatsapp fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Line" data-sharer="line" data-url="https://acking-you.github.io/posts/pat%E7%94%B2%E7%BA%A7-insertion-or-heap-sort/" data-title="PAT甲级--Insertion-or-Heap-Sort"><i class="fab fa-line fa-fw"></i></a><a href="javascript:void(0);" title="分享到 微博" data-sharer="weibo" data-url="https://acking-you.github.io/posts/pat%E7%94%B2%E7%BA%A7-insertion-or-heap-sort/" data-title="PAT甲级--Insertion-or-Heap-Sort" data-image="https://img-blog.csdnimg.cn/d42c44f8494c4416af716bc7156a4c96.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"><i class="fab fa-weibo fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Myspace" data-sharer="myspace" data-url="https://acking-you.github.io/posts/pat%E7%94%B2%E7%BA%A7-insertion-or-heap-sort/" data-title="PAT甲级--Insertion-or-Heap-Sort" data-description="PAT甲级--Insertion-or-Heap-Sort"><i data-svg-src="/lib/simple-icons/icons/myspace.min.svg"></i></a><a href="javascript:void(0);" title="分享到 Blogger" data-sharer="blogger" data-url="https://acking-you.github.io/posts/pat%E7%94%B2%E7%BA%A7-insertion-or-heap-sort/" data-title="PAT甲级--Insertion-or-Heap-Sort" data-description="PAT甲级--Insertion-or-Heap-Sort"><i class="fab fa-blogger fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Evernote" data-sharer="evernote" data-url="https://acking-you.github.io/posts/pat%E7%94%B2%E7%BA%A7-insertion-or-heap-sort/" data-title="PAT甲级--Insertion-or-Heap-Sort"><i class="fab fa-evernote fa-fw"></i></a></span>
        </div></div><div class="post-nav"><a href="/posts/%E5%A0%86%E7%9A%84%E8%BF%90%E7%94%A8%E6%9C%89%E5%BA%8F%E5%85%83%E7%B4%A0%E7%9A%84%E5%A4%9A%E8%B7%AF%E5%BD%92%E5%B9%B6topk%E9%97%AE%E9%A2%98/" class="prev" rel="prev" title="堆的运用——有序元素的多路归并topk问题"><i class="fas fa-angle-left fa-fw"></i>Previous Post</a>
            <a href="/posts/java%E5%8A%A8%E6%80%81%E4%BB%A3%E7%90%86%E8%AF%A6%E8%A7%A3/" class="next" rel="next" title="Java动态代理详解">Next Post<i class="fas fa-angle-right fa-fw"></i></a></div></div>
</div></article></div>
            </main>
            <footer class="footer"><div class="footer-container"><div class="footer-line">由 <a href="https://gohugo.io/" target="_blank" rel="noopener noreffer" title="Hugo 0.86.0">Hugo</a> 强力驱动 | 主题 - <a href="https://github.com/khusika/FeelIt" target="_blank" rel="noopener noreffer" title="FeelIt 1.0.1"><i class="fas fa-hand-holding-heart fa-fw"></i> FeelIt</a>
        </div><div class="footer-line" itemscope itemtype="http://schema.org/CreativeWork"><i class="far fa-copyright fa-fw"></i><span itemprop="copyrightYear">2023</span><span class="author" itemprop="copyrightHolder">&nbsp;<a href="/"></a></span></div>
</div>
</footer>
        </div>

        <div id="fixed-buttons"><a href="#" id="back-to-top" class="fixed-button" title="回到顶部">
                <i class="fas fa-chevron-up fa-fw"></i>
            </a></div><link rel="stylesheet" href="/lib/fontawesome-free/all.min.css"><link rel="stylesheet" href="/lib/animate/animate.min.css"><link rel="stylesheet" href="/lib/katex/katex.min.css"><link rel="stylesheet" href="/lib/katex/copy-tex.min.css"><script src="/lib/autocomplete/autocomplete.min.js"></script><script src="/lib/lunr/lunr.min.js"></script><script src="/lib/lunr/lunr.stemmer.support.min.js"></script><script src="/lib/lunr/lunr.zh.min.js"></script><script src="/lib/lazysizes/lazysizes.min.js"></script><script src="/lib/clipboard/clipboard.min.js"></script><script src="/lib/sharer/sharer.min.js"></script><script src="/lib/katex/katex.min.js"></script><script src="/lib/katex/auto-render.min.js"></script><script src="/lib/katex/copy-tex.min.js"></script><script src="/lib/katex/mhchem.min.js"></script><script>window.config={"code":{"copyTitle":"复制到剪贴板","maxShownLines":200},"comment":{},"math":{"delimiters":[{"display":true,"left":"$$","right":"$$"},{"display":true,"left":"\\[","right":"\\]"},{"display":false,"left":"$","right":"$"},{"display":false,"left":"\\(","right":"\\)"}],"strict":false},"search":{"highlightTag":"em","lunrIndexURL":"/index.json","lunrLanguageCode":"zh","lunrSegmentitURL":"/lib/lunr/lunr.segmentit.js","maxResultLength":100,"noResultsFound":"没有找到结果","snippetLength":50,"type":"lunr"}};</script><script src="/js/theme.min.js"></script></body></html>
